package Sort;

import java.util.Stack;

public class Sort {
    /**冒泡排序
     * 时间复杂度：O(N^2)
     *      进行优化后，当数组本身有序时间复杂度最好为：O(N)
     * 空间复杂度：O(1)
     * 稳定性：稳定
     * @param array
     */
    public void bubbleSort(int[] array) {
        //一共要走N - 1趟
        for (int i = 1; i < array.length; i++) {
            boolean flag = false;
            //每趟对未有序的数据进行比较交换
            for (int j = 0; j < array.length - i; j++) {
                if(array[j] > array[j + 1]) {
                    swap(array,j,j + 1);
                    flag = true;
                }
            }
            if(!flag) {//说明没有在进行交换了，已经有序了
                return;
            }
        }
    }

    /**选择排序
     * 时间复杂度：O(N^2)
     * 空间复杂度：O(1)
     * 稳定性：不稳定
     * @param array
     */
    public void selectionSort(int[] array) {
        for (int i = 0; i < array.length; i++) {
            int minIndex = i;//minIndex初始为未排序的起始下标i
            for (int j = i + 1; j < array.length; j++) {//从i + 1这个下标开始找最小值下标
                if(array[minIndex] > array[j]) {
                    minIndex = j;//找到未排序中最小值的下标
                }
            }
            //交换未排序的第一个与最小值
            swap(array, minIndex, i);
        }
    }

    /**直接插入排序
     * 时间复杂度：1、最坏情况下（逆序）：O(N^2)  2、最好情况下（正序）：O(N)
     * 空间复杂度：O(1)
     * 稳定性：稳定
     * @param array
     */
    public void directInsertionSort(int[] array) {
        for (int i = 1; i < array.length; i++) {
            int temp = array[i];
            int j = i - 1;
            //将比temp大的元素往后移
            while (j >=0 && array[j] > temp) {
                array[j + 1] = array[j];
                j--;
            }
            //此时j下标的值比temp小，插入到其前面
            array[j + 1] = temp;

          /*int j = i -1;
            for (;j >= 0; j--) {
                if(temp < array[j]) {//在已排序的数组中这个元素比temp大，进行覆盖后面的值
                    array[j + 1] = array[j];
                }else {//在已排序的数组中这个元素比temp小，需要在其前面插入temp
                    array[j + 1] = temp;
                    break;//说明完成了一个元素的插入，进行下一个的插入
                }
            }
            //在首元素进行插入 ----> 此时j == -1
            if(j == -1) {
                array[0] = temp;
            }*/
        }
    }

    /**希尔排序
     *时间复杂度为：
     *      根据实际来确定的，一般认为在 O(N*1.3) ~ O(N*1.5)
     * 空间复杂度：O(1)
     * 稳定性：不稳定
     * @param array
     */
    public void shellSort(int[] array) {
        int gap = array.length;
        while (gap > 1) {
            gap = gap / 2;//每次缩小分组，让数组逐渐有序
            shell(array,gap);
        }
    }
    private void shell(int[] array,int gap) {
        //直接插入排序
        for (int i = gap; i < array.length; i++) {//这里i++，使得组与组之间交替进行插入排序
            //由于是组内的直接插入排序，所以元素与元素直接差值是gap，而不是1了。
            int temp = array[i];
            int j = i - gap;
            //将比temp大的元素往后移
            while (j >= 0 && array[j] > temp) {
                array[j + gap] = array[j];
                j = j - gap;
            }
            array[j + gap] = temp;
        }
    }

    /**快速排序
     *时间复杂度为：
     *      最好情况下为：O(N*logN)，每次找的基准都是中间的值
     *      最坏情况下为：O(N^2)，正序或逆序（即是一棵单分支的树）
     * 空间复杂度：
     *      最好情况下为：O(logN)，每次找的基准都是中间的值
     *      最坏情况下为：O(n)，正序或逆序（即是一棵单分支的树）
     * 稳定性：不稳定
     * @param array
     */
    public void quickSort(int[] array) {
        if(array == null || array.length == 0) {
            return;
        }
        quickNor(array,0,array.length - 1);
    }

    private void quick(int[] array,int start,int end) {
        if(start >= end) {
             return;
        }
        //小数组优化
        int VALUE = 10;
        if(end - start + 1 == VALUE) {
            //直接插入排序
            directInsertionSort(array,start,end);
            return;
        }
        //三数取中
        int standard = medianOfNumbers(array,start,end);
        swap(array,start,standard);
        int par = standardDigging(array,start,end);
        quick(array,start,par - 1);
        quick(array,par + 1,end);
    }
    public void directInsertionSort(int[] array,int start,int end) {
        for (int i = start + 1; i <= end; i++) {
            int temp = array[i];
            int j = i - 1;
            //将比temp大的元素往后移
            while (j >= 0 && array[j] > temp) {
                array[j + 1] = array[j];
                j--;
            }
        }
    }
    private int medianOfNumbers(int[] array,int low,int high) {
        int mid = (low + high) / 2;
        //确保array[low] <= array[high]
        if(array[low] > array[high]) {
            swap(array,low,high);
        }
        //确保array[low] <= array[mid]
        if(array[low] > array[mid]) {
            swap(array,low,mid);
        }
        //到这里说明array[low]是最小的
        //确保array[mid] <= array[high]
        if(array[mid] > array[high]) {
            swap(array,mid,high);
        }
        //说明array[mid]是中间值，返回mid下标
        return mid;
    }
    private int standardHoare(int[] array,int low,int high) {
        int pivot = array[low];
        int i = low;
        while (low < high) {
            while (low < high && array[high] >= pivot) {
                high--;
            }
            while (low < high && array[low] <= pivot) {
                low++;
            }
            swap(array,low,high);
        }
        swap(array,i,low);
        return low;
    }
    private int standardDigging(int[] array,int low,int high) {
        int temp = array[low];
        while (low < high) {
            while (low < high && array[high] >= temp) {
                high--;
            }
            array[low] = array[high];
            while (low < high && array[low] <= temp) {
                low++;
            }
            array[high] = array[low];
        }
        array[low] = temp;
        return low;
    }
    private int standardPoint(int[] array,int low,int high) {
        int pivot = array[low];
        int prev = low;//prev用来标记小于等于基准值
        for(int cur = prev + 1;cur <= high;cur++) {//cur用来标记大于基准值
            if(array[cur] <= pivot) {
                prev++;//扩大小于等于基准值的区域
                swap(array,cur,prev);//将小于等于基准值的值放到前面来
            }
        }
        swap(array,low,prev);//将基准值放到最终位置
        return prev;//返回基准值索引
    }
    private void quickNor(int[] array,int start,int end) {
        int par = standardDigging(array,start,end);
        Stack<Integer> stack = new Stack<>();
        if(start < par - 1) {
            stack.push(start);
            stack.push(par - 1);
        }
        if(end > par + 1) {
            stack.push(par + 1);
            stack.push(end);
        }
        while (!stack.empty()) {
            end = stack.pop();
            start = stack.pop();
            par = standardDigging(array,start,end);
            if(start < par - 1) {
                stack.push(start);
                stack.push(par - 1);
            }
            if(end > par + 1) {
                stack.push(par + 1);
                stack.push(end);
            }
        }
    }

    /**归并排序
     * 时间复杂度：O(N*logN)
     * 空间复杂度：O(N)
     * 稳定性：稳定
     * @param array
     */
    public void mergeSort(int[] array) {
        mergeSortChild(array,0,array.length - 1);
    }
    private void mergeSortChild(int[] array,int left,int right) {
        if(left == right) {
            return;
        }
        int mid = (left + right) / 2;
        mergeSortChild(array,left,mid);
        mergeSortChild(array,mid + 1,right);
        //合并两个有序数组
        merge(array,left,mid,right);
    }
    private void merge(int[] array,int left,int mid,int right) {
        int s1 = left;
        int e1 = mid;
        int s2 = mid + 1;
        int e2 = right;
        int[] temp = new int[right - left + 1];
        int index = 0;
        while (s1 <= e1 && s2 <= e2) {
            if(array[s1] > array[s2]) {
                temp[index] = array[s2];
                s2++;
            }else {
                temp[index] = array[s1];
                s1++;
            }
            index++;
        }
        while (s2 <= e2) {
            temp[index] = array[s2];
            index++;
            s2++;
        }
        while (s1 <= e1) {
            temp[index] = array[s1];
            index++;
            s1++;
        }
        //此时temp数组就是排好序的数组
        for (int i = 0; i < temp.length; i++) {
            array[i + left] = temp[i];
        }
    }
    public void mergeSortNor(int[] array) {
        int gap = 1;
        while (gap < array.length) {//当gap >= array.length，说明整个数组都完成了归并
            for (int i = 0; i < array.length; i++) {
                int left = i;
                int mid = left + gap -1;
                //当gap很大的时候，mid下标可能越界
                if(mid >= array.length) {
                    mid = array.length - 1;
                }
                int right = mid + gap;
                //当gap很大的时候，right下标可能越界
                if(right >= array.length) {
                    right = array.length - 1;
                }
                merge(array,left,mid,right);
            }
            gap*=2;
        }
    }
    private void swap(int[] array, int a ,int b) {
        int temp = array[a];
        array[a] = array[b];
        array[b] = temp;
    }
}
